import java.util.LinkedList;
import java.util.Queue;

//迷宫中离⼊⼝最近的出⼝（medium）
//https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution {
    public int nearestExit(char[][] maze, int[] e) {
        //数组的规格（迷宫）
        int m = maze.length;
        int n = maze[0].length;

        //向四周扩散（上、下、左、右，靠加这组下标移动）
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};

        //标记哪里走过了
        boolean[][] visited = new boolean[m][n];//默认false

        //进行广度遍历
        //初始
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{e[0],e[1]});
        visited[e[0]][e[1]] = true;

        //记录for循环的次数——最短路径的步数
        int step = 0;
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int a = cur[0]; int b = cur[1];//记录弹出的元素的坐标（以便扩展——广度遍历）
                for (int k = 0; k < 4; k++) {
                    int x = a + dx[k]; int y = b + dy[k];
                    if(x >= 0 && x < m && y >=0 && y < n && maze[x][y] == '.' && !visited[x][y]){

                        //判断是否已经走到出口
                        if(x == 0 || y == 0 || x == m-1 || y == n-1 ) return step;
                        queue.add(new int[]{x,y});
                        visited[x][y] = true;
                    }
                }
            }

        }
        return -1;
    }
}